Complete Partial Order
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
s, characterized by particular completeness properties. Complete partial orders play a central role in
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...
: in
denotational semantics In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...
and
domain theory Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
.


Definitions

A complete partial order, abbreviated cpo, can refer to any of the following concepts depending on context. * A partially ordered set is a directed-complete partial order (dcpo) if each of its directed subsets has a
supremum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
. A subset of a partial order is directed if it is
non-empty In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
and every pair of elements has an upper bound in the subset. In the literature, dcpos sometimes also appear under the label up-complete poset. * A partially ordered set is a pointed directed-complete partial order if it is a dcpo with a
least element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an eleme ...
. They are sometimes abbreviated cppos. * A partially ordered set is a ω-complete partial order (ω-cpo) if it is a poset in which every ω-chain (''x''1 ≤ ''x''2 ≤ ''x''3 ≤ ''x''4 ≤ ...) has a supremum that belongs to the poset. Every dcpo is an ω-cpo, since every ω-chain is a directed set, but the
converse Converse may refer to: Mathematics and logic * Converse (logic), the result of reversing the two parts of a definite or implicational statement ** Converse implication, the converse of a material implication ** Converse nonimplication, a logical c ...
is not true. However, every ω-cpo with a
basis Basis may refer to: Finance and accounting * Adjusted basis, the net cost of an asset after adjusting for various tax-related items *Basis point, 0.01%, often used in the context of interest rates * Basis trading, a trading strategy consisting ...
is also a dcpo (with the same basis). An ω-cpo (dcpo) with a basis is also called a continuous ω-cpo (continuous dcpo). Note that ''complete partial order'' is never used to mean a poset in which ''all'' subsets have suprema; the terminology
complete lattice In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
is used for this concept. Requiring the existence of directed suprema can be motivated by viewing directed sets as generalized approximation sequences and suprema as ''limits'' of the respective (approximative) computations. This intuition, in the context of denotational semantics, was the motivation behind the development of
domain theory Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...
. The dual notion of a directed-complete partial order is called a filtered-complete partial order. However, this concept occurs far less frequently in practice, since one usually can work on the dual order explicitly.


Examples

* Every finite poset is directed complete. * All
complete lattice In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
s are also directed complete. * For any poset, the set of all non-empty
filters Filter, filtering or filters may refer to: Science and technology Computing * Filter (higher-order function), in functional programming * Filter (software), a computer program to process a data stream * Filter (video), a software component tha ...
, ordered by
subset inclusion In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset ...
, is a dcpo. Together with the empty filter it is also pointed. If the order has binary meets, then this construction (including the empty filter) actually yields a
complete lattice In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
. * Every set ''S'' can be turned into a pointed dcpo by adding a least element ⊥ and introducing a flat order with ⊥ ≤ ''s'' and s ≤ ''s'' for every ''s'' in ''S'' and no other order relations. * The set of all
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
s on some given set ''S'' can be ordered by defining ''f'' ≤ ''g'' if and only if ''g'' extends ''f'', i.e. if the
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function * Do ...
of ''f'' is a subset of the domain of ''g'' and the values of ''f'' and ''g'' agree on all inputs for which they are both defined. (Equivalently, ''f'' ≤ ''g'' if and only if ''f'' ⊆ ''g'' where ''f'' and ''g'' are identified with their respective
graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
.) This order is a pointed dcpo, where the least element is the nowhere-defined partial function (with empty domain). In fact, ≤ is also
bounded complete In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets that have some upper bound also have a least upper bound. Such a partial order can also be called consistently or coherently complete ( Viss ...
. This example also demonstrates why it is not always natural to have a greatest element. * The
specialization order In the branch of mathematics known as topology, the specialization (or canonical) preorder is a natural preorder on the set of the points of a topological space. For most spaces that are considered in practice, namely for all those that satisfy the ...
of any
sober space In mathematics, a sober space is a topological space ''X'' such that every (nonempty) irreducible closed subset of ''X'' is the closure of exactly one point of ''X'': that is, every irreducible closed subset has a unique generic point. Definitio ...
is a dcpo. * Let us use the term “
deductive system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A for ...
” as a set of
sentences ''The Four Books of Sentences'' (''Libri Quattuor Sententiarum'') is a book of theology written by Peter Lombard in the 12th century. It is a systematic compilation of theology, written around 1150; it derives its name from the '' sententiae'' ...
closed under consequence (for defining notion of consequence, let us use e.g.
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
's algebraic approachTarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)Stanley N. Burris
and H.P. Sankappanavar

/ref>). There are interesting theorems that concern a set of deductive systems being a directed-complete partial ordering.See online in p. 24 exercises 5–6 of §5 i

Or, on paper, see #_note-Tar-BizIg, Tar:BizIg.
Also, a set of deductive systems can be chosen to have a least element in a natural way (so that it can be also a pointed dcpo), because the set of all consequences of the empty set (i.e. “the set of the logically provable/logically valid sentences”) is (1) a deductive system (2) contained by all deductive systems.


Properties

An ordered set ''P'' is a pointed dcpo if and only if every
chain A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
has a supremum in ''P'', i.e., ''P'' is chain-complete. Alternatively, an ordered set ''P'' is a pointed dcpo if and only if every
order-preserving In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
self-map of ''P'' has a least
fixpoint A fixed point (sometimes shortened to fixpoint, also known as an invariant point) is a value that does not change under a given transformation. Specifically, in mathematics, a fixed point of a function is an element that is mapped to itself by th ...
.


Continuous functions and fixed-points

A
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
''f'' between two dcpos ''P'' and ''Q'' is called (Scott) continuous if it maps directed sets to directed sets while preserving their suprema: * f(D) \subseteq Q is directed for every directed D \subseteq P. * f(\sup D) = \sup f(D) for every directed D \subseteq P. Note that every continuous function between dcpos is a
monotone function In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
. This notion of continuity is equivalent to the topological continuity induced by the
Scott topology Scott may refer to: Places Canada * Scott, Quebec, municipality in the Nouvelle-Beauce regional municipality in Quebec * Scott, Saskatchewan, a town in the Rural Municipality of Tramping Lake No. 380 * Rural Municipality of Scott No. 98, Saskat ...
. The set of all continuous functions between two dcpos ''P'' and ''Q'' is denoted /nowiki>''P'' → ''Q''/nowiki>. Equipped with the
pointwise order In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the ''pointwise operations'', that is, operations defined ...
, this is again a dcpo, and a cpo whenever ''Q'' is a cpo. Thus the complete partial orders with Scott-continuous maps form a
cartesian closed In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in math ...
category Category, plural categories, may refer to: Philosophy and general uses * Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) *Categories (Peirce) * ...
. Barendregt, Henk
''The lambda calculus, its syntax and semantics''
,
North-Holland North Holland ( nl, Noord-Holland, ) is a province of the Netherlands in the northwestern part of the country. It is located on the North Sea, north of South Holland and Utrecht, and west of Friesland and Flevoland. In November 2019, it had a p ...
(1984)
Every order-preserving self-map ''f'' of a cpo (''P'', ⊥) has a least fixed-point.See
Knaster–Tarski theorem In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following: :''Let'' (''L'', ≤) ''be a complete lattice and let f : L → L be an monotonic function ...
; The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, , Chapter 4; the Knaster–Tarski theorem, formulated over cpo's, is given to prove as exercise 4.3-5 on page 90.
If ''f'' is continuous then this fixed-point is equal to the supremum of the iterates (⊥, ''f'' (⊥), ''f'' (''f'' (⊥)), … ''f'' ''n''(⊥), …) of ⊥ (see also the
Kleene fixed-point theorem In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following: :Kleene Fixed-Point Theorem. Suppose (L, \sqsubseteq) is a directed-complete pa ...
).


See also

Directed completeness alone is quite a basic property that occurs often in other order-theoretic investigations, using for instance algebraic posets and the
Scott topology Scott may refer to: Places Canada * Scott, Quebec, municipality in the Nouvelle-Beauce regional municipality in Quebec * Scott, Saskatchewan, a town in the Rural Municipality of Tramping Lake No. 380 * Rural Municipality of Scott No. 98, Saskat ...
. Directed completeness relates in various ways to other completeness notions such as
chain complete In mathematics, specifically order theory, a partially ordered set is chain-complete if every chain in it has a least upper bound. It is ω-complete when every increasing sequence of elements (a type of countable chain) has a least upper bound; ...
ness.


Notes


References

* {{DEFAULTSORT:Complete Partial Order Order theory ru:Частично упорядоченное множество#Полное частично упорядоченное множество